package Demo1;

import java.util.Comparator;
import java.util.PriorityQueue;

class com implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
public class Solution {
    /*public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> minsHeap = new PriorityQueue<>();

        for (int a : arr){
            minsHeap.offer(a);
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minsHeap.poll();
        }

        return ret;
    }*/

/*    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (k == 0){
            return ret;
        }

        PriorityQueue<Integer> minsHeap = new PriorityQueue<>(new com());

        for (int i = 0; i < k; i++) {
            minsHeap.offer(arr[i]);
        }


        for (int i = k; i < arr.length; i++) {
            int top = minsHeap.peek();
            if (top > arr[i]){
                minsHeap.poll();
                minsHeap.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = minsHeap.poll();
        }
        return ret;
    }*/


    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}

class Main{
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] ret = test.smallestK(new int[]{1,3,5,7,2,4,6,8}, 4);

        for(int s : ret){
            System.out.print(s + " ");
        }
    }
}